package Graph;
//import java.awt.print.Printable;
import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.InputStreamReader;
import java.util.Collections;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Queue;
import java.util.Random;
import java.util.Set;
import java.util.Stack;

public class Graph {
	
	
	private Map<Vertex , Set<Vertex>> adjList = new HashMap<Vertex, Set<Vertex>>();
	private List<Vertex> vertList = new LinkedList<Vertex>();
	private List<Edge> edgeList = new LinkedList<Edge>();

	/*
	 * Private Edge class used to construct adjacency list.
	 */
	private class Edge{
		private Vertex v;
		private Vertex u;
		public Edge(Vertex u, Vertex v){
			this.v = v;
			this.u = u;
		}
		
		public Vertex getU(){
			return u;
		}
		
		public Vertex getV(){
			return v;
		}
		
		public boolean equals(Object o){
			if (o instanceof Edge){
				return (((Edge)o).u.equals(this.u)) && (((Edge)o).v.equals(this.v)); 
			}
			return false;
		}
		
		public String toString(){
			return "[" + u + ", " + v + "]";
		}
		
	}
	
	public Graph(String file) {
		adjList = new HashMap<Vertex, Set<Vertex>>();
		vertList = new LinkedList<Vertex>();
		edgeList = new LinkedList<Edge>();
		try{
			BufferedReader br = new BufferedReader(new InputStreamReader(new FileInputStream(file)));
			String line = br.readLine();
			while (line != null){
				
				String [] e = line.split(" ");
				if (e.length != 2){
					throw new Exception("Invalid Edge!");
				}else{
					Vertex u = new Vertex(e[0]);
					Vertex v = new Vertex(e[1]);
					Vertex v_p = u;
					Vertex u_p = v;
					if (!vertList.contains(u)){
						vertList.add(u);
					}
					if (!vertList.contains(v)){
						vertList.add(v);
					}
					u_p = vertList.get(vertList.indexOf(u));
					v_p = vertList.get(vertList.indexOf(v));
				
					edgeList.add(new Edge(u_p, v_p));
//					edgeList.add(new Edge(v_p, u_p));
				}
				line = br.readLine();
			}
			GenerateAdjacencyList();
		}catch(Exception e){
			e.printStackTrace();
		}
		
	}
	
	/**
	 * Build a new graph based on 'g'
	 * 
	 * @param g
	 */
	public Graph(Graph g){
		this.adjList = new HashMap<Vertex, Set<Vertex>>(g.getAdjacencyList());
		this.vertList.addAll(g.getVertList());
		this.edgeList.addAll(g.getEdgeList());
	}
	
	/**
	 * Create a graph from a list of vertices 'c' that forms a Cycle in the graph G
	 * @param c the list of vertices in the cycle, in the order they appear in the cycle
	 */
	public Graph(List<Vertex> c){
		vertList = c;
		edgeList = new LinkedList<Edge>();
		for (int i = 0; i < vertList.size() - 1; i++){
			edgeList.add(new Edge(vertList.get(i), vertList.get(i+1)));
		}
		//edgeList.add(new Edge(vertList.get(vertList.size() -1), vertList.get(0)));
		HashSet<Vertex> reduceVerts = new HashSet<Vertex>(c);
		vertList.clear();
		vertList.addAll(reduceVerts);
		GenerateAdjacencyList();
	}
	
	
	public Graph(){
		adjList = new HashMap<Vertex, Set<Vertex>>();
	}
	
	/**
	 * Add the graph 'g' to this graph.
	 * @param g
	 * @return
	 */
	public Graph combine(Graph g){
		Graph ret = new Graph();
		ret.vertList.addAll(this.vertList);
		ret.edgeList.addAll(this.edgeList);
		for (Vertex v: g.vertList){
			if (!ret.getVertList().contains(v)){
				ret.vertList.add(v);
			}
		}
		for (Edge e: g.edgeList){
			if (!ret.getEdgeList().contains(e)){
				ret.edgeList.add(e);
			}
		}
		ret.GenerateAdjacencyList();
		return ret;
	}
	
	/**
	 * Generate an adjacency list for the graph based on its current Edge and Vertex lists.
	 */
	public void GenerateAdjacencyList(){
		adjList.clear();
		for (Vertex v: vertList){
			v.setDegree(0);
			adjList.put(v, new HashSet<Vertex>());
		}
		for (Vertex v: vertList){
			for (Edge e: edgeList){
				if (v.equals(e.getU())){
					Vertex temp = vertList.get(vertList.indexOf(e.getV()));
					adjList.get(v).add(temp);
					adjList.get(temp).add(v);
					v.setDegree(v.getDegree() + 1);
					temp.setDegree(temp.getDegree() + 1);
				}
			}
		}
	}
	
	/**
	 * Find a cycle in the Graph g
	 * 
	 * @return A cycle in the calling graph
	 */
	public Graph FindCycle(){
		for (Vertex v: this.adjList.keySet()){
				v.setColor("White");
				v.setParent(null);
		}
		for (Vertex u: this.adjList.keySet()){
			if (u.getColor().equals("White")){
				List<Vertex> c = DFSVisit(u, null);
				//print("Back From DFSVisit");
				if (c != null){
					return new Graph(c);
				}
			}
		}
		return null;
	}
	
	/**
	 * Test whether this graph is a PATH.
	 */ 
	public boolean testPath(){
//		print("Testing Pathity");
		boolean retVal = true;
		for (Vertex v: vertList){
			if(v.getDegree() <= 2){
				retVal = retVal && true;
			}
			else{
				retVal = retVal && false;
			}
		}
//		print("P is a path? " + retVal);
		return retVal;
	}
	
	/**
	 * Visit a vertex 'u' in the graph 'g'
	 * 
	 * @param u - the vertex to visit
	 * @param g - the Graph where g exists
	 */
	private List<Vertex> DFSVisit(Vertex u, Vertex parent){		
		u.setColor("Gray");
		List<Vertex> ret = null;
		for (Vertex v : this.adjList.get(u)){
			if (v.getColor().equals("White")){
				ret = new LinkedList<Vertex>();
				v.setParent(u);
				List<Vertex> visit = DFSVisit(v, u);
				if (visit != null){
					ret.addAll(visit);
				}
				
			}
			else if (v.equals(parent)){
				// Ignore the ones we've seen so far?
				continue;
			}
			else if (!v.getColor().equals("White")){
				Vertex p_u = u;
				Vertex p_v = v;
				Stack<Vertex> s = new Stack<Vertex>();  // Stack for storing vertices along u path
				Queue<Vertex> q = new LinkedList<Vertex>();  // Queue for storing vertices along v path
				while(p_u != null){
					s.push(p_u);
					p_u = p_u.getParent();
				}
				while(p_v != null){
					q.add(p_v);
					p_v = p_v.getParent();
				}
				Vertex start = (Vertex) FirstCommonElement(s, q);
				while (!s.isEmpty() && !s.peek().equals(start)){
					s.pop();
				}
				s.pop();
				List<Vertex> c = new LinkedList<Vertex>();
				if (start != null){
					c.add(start);
				}
				while(!s.isEmpty()){
					c.add(s.pop());
				}
				while (!q.isEmpty() && !q.peek().equals(start)){
					c.add(q.remove());
				}
				c.add(start);
				//print(c);
				return c;
			}
		}
		u.setColor("Black");
		return ret;
	}
	
	/**
	 * Takes a list of vertices in G and induces a subgraph
	 * @param h
	 * @param G
	 * @return
	 */
	private Graph subGraph(LinkedList<Vertex> h, Graph g){
		Graph sub = new Graph();
		sub.vertList.addAll(h);
		for (Vertex v: h){
			for (Vertex u: g.vertList){
				Edge e = new Edge(v, u);
				if (g.edgeList.contains(e)){
					if (!sub.edgeList.contains(e)){
						sub.edgeList.add(g.edgeList.get(edgeList.indexOf(e)));
					}
				}
			}
		}
		sub.GenerateAdjacencyList();
		//print(sub);
		return sub;
		
	}
	
	/**
	 *  non-recursive function which 
	 *  constructs a list of connected components (which are lists)
	 * @return
	 */
	public LinkedList<Graph> connectedComponents(){
		LinkedList<Graph> cc = new LinkedList<Graph>(); 
		//print("this: " + this.toString());
		for (Vertex v: this.adjList.keySet()){
			if (!v.getColor().equalsIgnoreCase("v")){
				cc.add(this.subGraph(doConnectedComponents(v),this));
			}
		}
		// Remove nulls from cc...
		LinkedList<Graph> components = new LinkedList<Graph>();
		for (Graph g: cc){
			if (g != null){
				components.add(g);
			}
		}
		//print("components: " + components);
		return components;
	}
	/**
	 *  a recursive function which constructs a linked list
	 * @param v
	 * @return
	 */
	private LinkedList<Vertex> doConnectedComponents(Vertex v){
		v.setColor("v");
		LinkedList<Vertex> vList = new LinkedList<Vertex>();
		vList.add(v);
		for (Vertex u: this.adjList.get(v)){
			if (!u.getColor().equalsIgnoreCase("v")){
				vList.addAll(this.doConnectedComponents(u));
			}
		}	
		//print("VList of " + v.toString() + ": " + vList.toString());
		return vList;
		
	}

	/**
	 * Find the pieces of the Graph g with respect to Cycle c
	 * 
	 * @param g The graph to find pieces of
	 * @param c The Cycle to find pieces with respect to
	 * @return
	 */
	public LinkedList<Graph> findPieces(Graph c){
		Graph pG = new Graph(this);
		for(Edge e : c.edgeList){
			pG = pG.removeEdge(e);
		}
//		print("PieceGraph: " + pG.toString());
		return pG.connectedComponents();
	}
	
	/**
	 * Remove the vertex v from this graph, as well as all edges adjacent to v.
	 * @param v
	 * @return
	 */
	public Graph removeVertex(Vertex v){
		List<Vertex> newVertList = new LinkedList<Vertex>();
		newVertList.addAll(vertList);
		newVertList.remove(v);
		List<Edge> newEdgeList = new LinkedList<Edge>();
		newEdgeList.addAll(edgeList);
		List<Edge> edgesToRemove = new LinkedList<Edge>();
		for (Edge e : newEdgeList){
			if (e.getU().equals(v) || e.getV().equals(v)){
				edgesToRemove.add(e);
			}
		}
		newEdgeList.removeAll(edgesToRemove);
		Graph g = new Graph();
		g.edgeList = newEdgeList;
		g.vertList = newVertList;
		g.GenerateAdjacencyList();
		return g;
	}
	
	
	private Graph removeEdge(Edge e){
		Edge e_rev = new Edge(e.getV(), e.getU());
		if (edgeList.contains(e)){
			edgeList.remove(e);
		}
		if (edgeList.contains(e_rev)){
			edgeList.remove(e_rev);
		}
		List<Vertex> newVertList = new LinkedList<Vertex>();
		newVertList.addAll(vertList);
		List<Edge> newEdgeList = new LinkedList<Edge>();
		newEdgeList.addAll(edgeList);
		Graph g = new Graph();
		g.edgeList = newEdgeList;
		g.vertList = newVertList;
		g.GenerateAdjacencyList();
		return g;
		
	}
	
	
	/**
	 * Find the first common element between the stack a and the queue v
	 * @param a
	 * @param b
	 * @return
	 */
    public static Object FirstCommonElement(Stack<Vertex> a, Queue<Vertex> b){
    	for (Vertex x : a){
    		if (b.contains(x)){
    			return x;
    		}
    	}
    	return null;
    	
    }
    
    /**
     * Test the graph g for bipartite.
     * @return true - if the graph is bipartite, false otherwise.
     */
    public boolean TestBipartite(){
    	// Get the start Vertex
    	Vertex s = this.vertList.get(0);
    	// Set up data structures.
    	Queue<Vertex> q = new LinkedList<Vertex>();
    	Set<Vertex> p_1 = new HashSet<Vertex>();   // Red Partition
    	Set<Vertex> p_2 = new HashSet<Vertex>();   // Blue Partition
    	s.setColor("Red");
    	for (Vertex u : this.getVertList()){
    		if (u != s){
    			u.setColor("White");
    		}
    	}
    	q.add(s);
    	Set<Vertex> p_i;
    	String currColor;
    	Graph g_prime = this;
    	while (!q.isEmpty()){
    		Vertex u = q.remove();
    		if (u.getColor().equals("Blue")){
    			p_i = p_2;
    			currColor = "Red";
    		}
    		else{
    			p_i = p_1;
    			currColor = "Blue";
    		}
    		
    		for (Vertex v: g_prime.getAdjacencyList().get(u)){
    			if (v.getColor().equals(u.getColor())){
    				return false;
    			}
    			else{
    				v.setColor(currColor);
    				q.add(v);
    				p_i.add(v);
    				g_prime = g_prime.removeVertex(u);
    			}
    		}
    	}
    	
    	
    	return true;
    }
    
    /**
     * This method should only be used on CYCLES.  This method takes a sub-path in the cycle and replaces it with a new
     * sub-path.
     * @param pathToReplace
     * @param replacement
     * @return
     */
    public Graph replacePath(List<Vertex> pathToReplace, List<Vertex> replacement){
    	List<Vertex> newCycleVerts = new LinkedList<Vertex>();
    	print(pathToReplace + "->" + replacement);
    	if (((pathToReplace.get(0).equals(replacement.get(0))) 
    			&& (pathToReplace.get(pathToReplace.size()-1).equals(replacement.get(replacement.size()-1))))){
    			for (Vertex v: this.getVertList()){
    				if (v.equals(pathToReplace.get(0))){
    					for (Vertex u: replacement){
    						newCycleVerts.add(u);
    					}
    				}
    				else if (pathToReplace.contains(v)){
    					continue;
    				}
    				else{
    					newCycleVerts.add(v);
    				}
    			}
    		}
    	newCycleVerts.add(pathToReplace.get(0));
    	print("NewCycleVerts: " + newCycleVerts);
    	return new Graph(newCycleVerts);
    }

    /**
     * Get the attachment points of 'p' on this graph (Should be a cycle).
     * @param p
     * @return
     */
    public List<Vertex> getAttachmentPoints(Graph p){
    	List<Vertex> attachPts = null;
    	if (p!= null){
	    	attachPts = new LinkedList<Vertex>();	
	    	for (Vertex v: p.getVertList()){
		    		if (this.vertList.contains(v)){
		    			attachPts.add(v);
		    		}
	    	}
    	}
    	return attachPts;
    }
    
    /**
     * Return an InterlacementVertex for the piece p
     * @param p
     * @return
     */
    private InterlacementVertex getVertexByPiece(Graph p){
    	for (Vertex v : vertList){
    		if (((InterlacementVertex)v).getPiece().equals(p)){
    			return (InterlacementVertex)v;
    		}
    	}
    	return null;
    }
    
    public boolean contains(Vertex v){
    	return vertList.contains(v);
    }
    
    /**
     * Create the interlacemnt graph for 'pieces' with respect to cycle.
     * @param cycle
     * @param pieces
     * @return
     */
    public Graph createInterlacementGraph(Graph cycle, List<Graph> pieces){
    	Graph ig = new Graph();
    	InterlacementVertex v_i;
    	InterlacementVertex v_j;
    	List<Vertex> attachPts;
//    	print(pieces);
    	for (Graph p : pieces){
    		// Create an interlacement vertex for p
    		ig.vertList.add(new InterlacementVertex(p));
    	}
//    	print("IG VERTS: " + ig.vertList);
//    	print("CYCLE: " + cycle);
    	Random r = new Random();
    	for (int i = 0; i < pieces.size(); i++){
    		attachPts = cycle.getAttachmentPoints(pieces.get(i));
//    		print("Piece " + i + ": " + pieces.get(i));
    		Vertex s = attachPts.get(r.nextInt(attachPts.size()));
    		//print(s);
    		//print("IG VERTS: " + ig.vertList);
    		//print("IG EDGES: " + ig.edgeList);
    		for (int j = 0; j < pieces.size(); j++){
    			if (i != j){
    				 v_i = ig.getVertexByPiece(pieces.get(i));
    				 v_j = ig.getVertexByPiece(pieces.get(j));
    				 Edge e = new Edge(v_i, v_j);
    				 if (!ig.edgeList.contains(e)){
    					 // Permute cycle to start with s
    					 List<Edge> traverseEdges = new LinkedList<Edge>();
    					 traverseEdges.addAll(cycle.getEdgeList());
    					 Edge startEdge = null;
    					 for (Edge edge : traverseEdges){
    						 if (edge.getU().equals(s)){
    							 startEdge = edge;
    							 break;
    						 }
    					 }
    					 int numIVerts = attachPts.size();
    					 int numJVerts = cycle.getAttachmentPoints(pieces.get(j)).size();
    					 int maxVerts = numJVerts;
    					 Edge newEdge = startEdge;
    					 
    					 while(numIVerts > 0){
//    						 print(newEdge);
    						 if (pieces.get(i).contains(newEdge.getU())){
    							 numIVerts--;
    						 }
    						 if (pieces.get(j).contains(newEdge.getU())){
    							 numJVerts--;
    						 }
    						 for (Edge edge: cycle.getEdgeList()){
    							 if (edge.getU().equals(newEdge.getV())){
    								 newEdge = edge;
    								 break;
    							 }
    						 }
    					 }
						 if (numJVerts != 0 && numJVerts != maxVerts){
							 // p_i and p_j are interlaced
							 ig.edgeList.add(new Edge(v_i, v_j));
							 break;
						 }
    				 }
    			}
    		}
    	}
    	ig.GenerateAdjacencyList();
    	return ig;
    }
    
    
    public boolean testK33(){
    	if (vertList.size() == 6){
    		for (Vertex v : vertList){
    			if (!(v.getDegree() == 3)){
    				return false;
    			}
    		}
    	}
    	else{
    		return false;
    	}
    	return true;
    }
    
    
	/**
	 * Test whether the Graph G is planar
	 * 
	 * @param g	
	 * @return true if the graph is planar, false if not
	 */
	public static boolean TestPlanarity(Graph g, Graph cycle){
//		print("Testing Planarity");
		boolean planar = true;
		if (g.getEdgeList().size() > ((3 * g.getVertList().size()) -6)){
			return false;
		}
		if (g.testK33()){
			print("Graph is K33");
			return false;
		}
//		print("Cycle: " + cycle);
		List<Graph> pieces = g.findPieces(cycle);
		print("Num Pieces: " + pieces.size());
		print(pieces);
		for (Graph p : pieces){
//			print(p.adjList);
//			print(p);
			List<Vertex> attach_pts = cycle.getAttachmentPoints(p);
			if (p.testK33()){
				return false;
			}
			else if(p.vertList.size() == 1){
				planar = true;
			}
			else if (p.testPath()){
				planar = true;
			}
			else{
//				break;
				/*
				 * Find two consecutive attachment points of 'p' on the cycle.
				 */
				Random r = new Random();
				Vertex a = attach_pts.get(r.nextInt(attach_pts.size()));
				Vertex next_vert = a;
				Vertex b = null;
				for (Edge e : cycle.getEdgeList()){
					if (e.getU().equals(next_vert)){
						next_vert = e.getV();
					}
					if (attach_pts.contains(e.getV())){
						b = e.getV();
						break;
					}
				}
//				System.out.println("a: " + a + ", b: " + b);
				List<Vertex> cyclePath = cycle.findLongPath(a, b);
				List<Vertex> pPath = p.findLongPath(a, b);
				print("CYCLE: " + cycle);
				Graph c_prime = cycle.replacePath(cyclePath, pPath);
				Graph p_prime = cycle.combine(p);
//				print("P_PRIME: " + p_prime);
//				print("Planar: " + planar);
				if (!planar){
					break;
				}
				print("CYCLE: " + cycle);
				print("C_PRIME: " + c_prime);
				print("P_PRIME: " + p_prime);
				planar = (planar && TestPlanarity(p_prime, c_prime));
			}

		}
		
		if (planar == true){
			Graph ig = g.createInterlacementGraph(cycle, pieces);
//			print("vert= " + ig.vertList + "\n edge= " + ig.edgeList);
		
//			print(pieces);
			return (g.createInterlacementGraph(cycle, pieces)).TestBipartite();
		}
		return planar;
	}
	
	/**
	 * Find a path in this graph from 'u' to 'v'.  This method uses breadth-first search.
	 * @param u The starting vertex of the path.
	 * @param v The ending vertex of the path.
	 * @return
	 */
	public List<Vertex> findPath(Vertex u, Vertex v){
		Graph temp = new Graph(this);
		Stack<Vertex> revPath = new Stack<Vertex>();
		List<Vertex> path = new LinkedList<Vertex>();
		if (u.equals(v)){
//			System.out.println("U = V !!!!1oneone!!11!");
			
		}
		for (Vertex a : this.vertList){
			a.setColor(Vertex.WHITE);
			a.setParent(null);
		}
		u.setColor(Vertex.GRAY);
		Queue<Vertex> q = new LinkedList<Vertex>();
		q.add(u);
		Vertex s = u;
		while (!q.isEmpty()){
			s = q.poll();
			for (Vertex t: adjList.get(s)){
				if (t.getColor().equals(Vertex.WHITE)){
					t.setColor(Vertex.GRAY);
					t.setParent(s);
					q.add(t);
				}
			}
			if (s.equals(v)){
				break;
			}
			s.setColor(Vertex.BLACK);
		}
		while (s != null){
			revPath.push(s);
			s = s.getParent();
		}
		path.addAll(revPath);
		Collections.reverse(path);
		return path;
	}
	
	
	public List<Vertex> findLongPath(Vertex u, Vertex v){
		Graph temp = new Graph(this);
		List<Vertex> path = findPath(u,v);
//		System.out.println(path);
		path.remove(u);
		path.remove(v);
		for (Vertex s : path){
			temp.removeVertex(s);
		}
//		temp.GenerateAdjacencyList();
		path = temp.findPath(u, v);
//		System.out.println(path);
		return path;
	}
	
	
	public String toString(){
		String retVal = "\n(Vertices: {";
		for (Vertex v: vertList){
			retVal = retVal + v.toString() + ", ";
		}
		int lastIndex = retVal.lastIndexOf(',') > -1? retVal.lastIndexOf(','): retVal.length() - 1; 
		retVal = retVal.substring(0, lastIndex) + "}\nEdges: { ";
		for (Edge e: edgeList){
			retVal = retVal + "[" + e.getU() + ", " + e.getV() + "], ";
		}
		lastIndex = retVal.lastIndexOf(',') > -1? retVal.lastIndexOf(','): retVal.length() - 1; 
		retVal = retVal.substring(0, lastIndex ) + "} )";
		return retVal;
	}
	
	public Vertex getVertex(String label){
		for (Vertex u : vertList){
			if (u.getLabel().equals(label)){
				return u;
			}
		}
		return null;
	}

	public List<Vertex> getVertList(){
		return vertList;
	}
	
	public List<Edge> getEdgeList(){
		return edgeList;
	}
	
	public Map<Vertex, Set<Vertex>> getAdjacencyList(){
		return adjList;
	}
	
	public static void print(Object o){
		//System.out.println(o);
	}
}
